package dataStructure.linkedlist;

//约瑟夫问题：单循环链表--环形链表
//本题解没带头结点
public class Josepfu {
    public static void main(String[] args) {
        CircleSingleLinkedList circleSingleLinkedList = new CircleSingleLinkedList();
        circleSingleLinkedList.add(5);
//        circleSingleLinkedList.print();
        circleSingleLinkedList.countBoy(1,2,5);
    }
}
class CircleSingleLinkedList{
    Boy first=null;  //定义一个指针，等待指向第一个节点

    // 添加小孩节点，构建成一个环形的链表
    public void add(int nums){
        if (nums<1){
            System.out.println("请输入正确的人数");
            return;
        }
        Boy p = null; // 辅助指针，帮助构建环形链表
        for (int i = 1;i<=nums;i++){
            Boy boy = new Boy(i);
            //如果是第一个节点
            if (i ==1){
                first = boy;  //指向第一个节点
                first.setNext(first); // 构成环
                p = boy; //让 p 指向第一个小孩
            }else {
                p.setNext(boy);
                boy.setNext(first);
                p = boy;    //指针后移
            }

        }
    }
    public void countBoy(int startNo, int countNum, int nums){
        if (first==null||startNo<1||countNum>nums){
            System.out.println("参数输入有误， 请重新输入");
            return;
        }
        Boy helper = first; //定义一个辅助指针

            //让该指针移动到first指针的后面
            for (int i =0;i<nums-1;i++){
                helper = helper.getNext();
            }
            //移动first和helper指针，移动到需要的startNo的位置
            for (int i =0;i<startNo-1;i++){
                first = first.getNext();
                helper = helper.getNext();
            }
        while (first!=helper){
            for (int i=0;i<countNum-1;i++){
                first = first.getNext();
                helper = helper.getNext();
            }
            System.out.println(first.getNo());
            first = first.getNext();//first指针后移一个
            helper.setNext(first);

        }
        System.out.println(first.getNo());


    }
    public void print(){
        if (first == null) {
            System.out.println("没有任何小孩~~");
            return;
        }
        Boy p = first;
        while (true){
            System.out.printf("小孩的编号 %d \n", p.getNo());
            if (p.getNext()==first){
                break;
            }
            p = p.getNext();
        }
    }
}
class Boy{
    private int no;
    private Boy next;
    Boy(int no){
        this.no = no;
    }
    public int getNo() {
        return no;
    }

    public void setNo(int no) {
        this.no = no;
    }

    public Boy getNext() {
        return next;
    }

    public void setNext(Boy next) {
        this.next = next;
    }
}
